/*
The prime 41, can be written as the sum of six consecutive primes:
41 = 2 + 3 + 5 + 7 + 11 + 13
This is the longest sum of consecutive primes that adds to a prime below one-hundred.
The longest sum of consecutive primes below one-thousand that adds to a prime, contains 21 terms, and is equal to 953.
Which prime, below one-million, can be written as the sum of the most consecutive primes?

Anser:997651
Time:100ns
*/
package main

import (
	"fmt"
	"time"
)

func main() {
	t := time.Now()
	defer fmt.Println(time.Since(t))
	// start here
	l := int(1e6)
	p := genPrime(l)
	s := SumOfConsecutivePrimes(p)
	max := 0
	var prime int
	for i, lenth := 0, len(s); i < lenth; i++ {
		for j := i + 1; j < lenth; j++ {
			k := s[j] - s[i]
			if k >= l {
				break
			}
			if !p[k] && max < j-i {
				max = j - i
				prime = k
			}
		}
	}
	fmt.Println(prime)
}
func genPrime(l int) []bool {
	s := make([]bool, l)
	s[0] = true
	s[1] = true
	for i := 2; i < l; i++ {
		if !s[i] {
			for j := 2; i*j < l; j++ {
				s[i*j] = true
			}
		}
	}
	return s
}
func SumOfConsecutivePrimes(p []bool) []int {
	s := make([]int, 1, 1000)
	sum := 0
	for i, v := range p {
		if !v {
			sum += i
			s = append(s, sum)
		}
	}
	return s
}
